#define KDTREE_DEFINE_OSTREAM_OPERATORS
#define TAM 16

#include <kdtree++/kdtree.hpp>
#include <iostream>
#include <vector>
#include <limits>
#include <functional>
#include <set>
#include <sys/time.h>


/*
struct quadruplet {
	typedef int value_type;

	quadruplet (value_type a, value_type b, value_type c, value_type e) {
    	d[0] = a;
	    d[1] = b;
    	d[2] = c;
		d[3] = e;
  	}

	quadruplet (const quadruplet & x) {
		d[0] = x.d[0];
		d[1] = x.d[1];
		d[2] = x.d[2];
		d[3] = x.d[3];
	}

	~quadruplet () {
	}

	inline value_type operator[](size_t const N) const { return d[N]; }
	value_type d[4];
};
*/

struct node
{
  typedef int tipo;

  node(const int tam, const int *a)
  {
    v = new int[tam];

    for(int i = 0; i< tam; i++)
     v[i] = a[i];
  }

  node(const int tam, const node & x)
  {
    v = new int[tam];

    for(int i = 0; i< tam; i++)
     v[i] = x.v[i];
  }

  ~node()
  {
  }

  inline tipo operator[](size_t const N) const { return v[N]; }

  tipo *v;
};

inline double tac( node t, size_t k ) { return t[k]; }

typedef KDTree::KDTree<TAM, node, std::pointer_to_binary_function<node,size_t,double> > tree;

std::ostream& operator<<(std::ostream& out, node const& T) {
  return out << '(' << T.v[0] << ',' << T.v[1] << ',' << T.v[2] << ',' << T.v[3] << ')';
}


/*
inline bool operator==(quadruplet const& A, quadruplet const& B) {
  return A.d[0] == B.d[0] && A.d[1] == B.d[1] && A.d[2] == B.d[2] && A.d[3] == B.d[3];
}

std::ostream& operator<<(std::ostream& out, quadruplet const& T) {
  return out << '(' << T.d[0] << ',' << T.d[1] << ',' << T.d[2] << ',' << T.d[3] << ')';
}

inline double tac( quadruplet t, size_t k ) { return t[k]; }

typedef KDTree::KDTree<4, quadruplet, std::pointer_to_binary_function<quadruplet,size_t,double> > tree_type;
*/


int main (int argc, char **argv) {
	FILE *fp;
	// variaveis aux. de insercao
	int vetor[TAM];
//	int a,b,c,d;
	// variaveis para calculo do tempo
	clock_t start,finish;

	node *t, *q;
	// struct do tipo kdtree
	tree src(std::ptr_fun(tac));

	// vetor da struct com resultados da busca
	std::vector<node> v;
	// elemento auxiliar para iteracao no vetor da struct
	std::vector<node>::const_iterator ci; 
	unsigned int range;

	// INSERCAO
	fp = fopen (argv[1], "r");
	if (fp == NULL) {
		puts("Erro! arquivo de leitura não foi aberto");
		exit(1);
	}
	else {
		start=clock();
		while (!feof(fp)) {
			//fscanf(fp, "%d %d %d %d", &a, &b, &c, &d);
			for (int i=0; i< TAM; i++)
				fscanf(fp, "%d", &vetor[i]);
			t = new node(TAM,vetor);
			src.insert(*t);
			//src.insert( quadruplet(a,b,c,d) );
		}
		finish=clock();
	}
	std::cout << "Tempo de leitura de arquivo e insercao na árvoe: "  << (double) (finish - start) / (double) (CLOCKS_PER_SEC/1000) << "ms." << std::endl;

	
	// BUSCA
//	quadruplet q (50,50,50,50);
	
	for (int i=0; i< TAM; i++)
		vetor[i]=50;
	q = new node(TAM, vetor);	
	range = 5;
	
	start=clock();
	src.find_within_range(*q, range, std::back_inserter(v));
	finish=clock();

	std::cout << "Tempo da busca na árvoe: "  << (double) (finish - start) / (double) (CLOCKS_PER_SEC/1000) << "ms." << std::endl;

		
	std::cout << "encontrados   " << v.size() << " nodos dentro do intervalo\n" ;
	
	/*
    ci = v.begin();
    for (; ci != v.end(); ++ci)
		std::cout << *ci << " ";
    std::cout << "\n" << std::endl;
	*/
	// STATUS
		
}
